对于每个点(x, y)，正左方最近的点记为(x’, y)，正下方最近的点记为(x, y’)，
如果以这3个点为顶点的矩形内部存在有其它的点(x’’, y’’)，则从(x, y)到(x’’, y’’)不存在满足要求的曼哈顿距离 
反之，如果整个图中都不存在这种情况，则任意两点间都有满足要求的曼哈顿距离. 因而可以用扫描线和可持久化线段树来做，
从左往右扫描，每个x值对应线段树的一个版本，
每遇到一个点(x, y)和它正下方最近的点(x, y’)就在当前版本的线段树和上一个版本为x’的线段树上查询y’+1和y之间的点数，
如果之间的点数不为1，则意味着存在上述的点(x’’,y’’). 对于每条扫描线处理完查询之后再将点插入到当前版本的线段树中. 复杂度O(NlogN). 
其中维护距离当前节点在水平和垂直方向最近的点了，可以用数组记录此时横纵坐标最新点的编号
坑点是需要从前往后做一遍，然后从后往前再做一遍，hack数据：
2
1 5
2 3
//https://172.16.79.125/contest/view.action?cid=789#problem/L
#include <bits/stdc++.h>
const int N=1e6+5,INF=0x3f3f3f3f,M=5e4+5;
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

PII a[N];
int n,flag;
int mx[M],my[M];
struct Node{
    int l,r;
    int v;
}t[N<<6];
int cnt,root[M];

void build(int &o,int pre,int l,int r,int pos){
    o=++cnt;
    t[o]=t[pre];
    t[o].v++;
    if(l==r) return ;
    int mid=l+r>>1;
    if(pos<=mid) build(t[o].l,t[pre].l,l,mid,pos);
    else build(t[o].r,t[pre].r,mid+1,r,pos);
}

int query(int ox,int oy,int l,int r,int ql,int qr){
    if(l>=ql&&r<=qr) return t[ox].v-t[oy].v;
    int res=0;
    int mid=l+r>>1;
    if(ql<=mid) res+=query(t[ox].l,t[oy].l,l,mid,ql,qr);
    if(qr>mid) res+=query(t[ox].r,t[oy].r,mid+1,r,ql,qr);
    return res;
}

void work(){
    cnt=0;
    memset(mx,0,sizeof mx);
    memset(my,0,sizeof my);
    memset(root,0,sizeof root);
    int last=root[0];
    for(int i=1;i<=n;i++){
        int x1=a[i].first,y1=a[i].second;
        int x2=a[my[y1]].first,y2=a[mx[x1]].second;
        build(root[x1],last,1,50000,y1);
        int cnt=query(root[x1],root[x2],1,50000,y2+1,y1);
        if(cnt!=1){
            flag=0;
            return ;
        }
        mx[a[i].first]=i;
        my[a[i].second]=i;
        last=root[x1];
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    
    clock_t c1=clock();

#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif // LOCAL

    while(cin >>n){
        if(!n) return 0;
        for(int i=1;i<=n;i++) cin >>a[i].first>>a[i].second;

        a[n+1].first=a[n+1].second=0;

        sort(a+1,a+n+1);
        n=unique(a+1,a+n+1)-a-1;
        flag=1;
        work();
        for(int i=1;i<=n;i++){
            a[i].first=50001-a[i].first;
        }
        sort(a+1,a+n+1);
        work();
        if(flag) cout <<"YES"<<endl;
        else cout <<"NO"<<endl;
    }

end:

    cerr <<"Time Used:"<<clock()-c1<<"ms"<<endl;

    return 0;
}



#include <bits/stdc++.h>
const int N=1e5+5,INF=0x3f3f3f3f;
using namespace std;
typedef long long ll;

priority_queue<int> q;
ll suma[N],sumb[N];
int n,c,f;
struct Node{
    int a,b;
    bool operator <(const Node &w){
        return a<w.a;
    }
}t[N];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    
    clock_t c1=clock();

#ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif // LOCAL

    cin >>n>>c>>f;
    int a,b;
    for(int i=1;i<=c;i++){
        cin >>a>>b;
        t[i]={a,b};
    }
    sort(t+1,t+c+1);

    ll resa=0;
    for(int i=1;i<=n/2;i++){
        q.push(t[i].b);
        resa+=t[i].b;
    }
    suma[n/2+1]=resa;
    for(int i=n/2+1;i<c;i++){
        int tops=q.top();
        if(t[i].b<tops){
            q.pop();
            resa-=tops;
            resa+=tops;
        }
        suma[i+1]=resa;
    }

    while(!q.empty()) q.pop();
    ll resb=0;
    for(int i=c;i>=c-(n/2)+1;i--){
        q.push(t[i].b);
        resa+=t[i].b;
    }
    suma[c-(n/2)]=resa;
    for(int i=c-(n/2);i>2;i--){
        int tops=q.top();
        if(t[i].b<tops){
            q.pop();
            resb-=tops;
            resb+=tops;
        }
        suma[i-1]=resb;
    }

end:

    cerr <<"Time Used:"<<clock()-c1<<"ms"<<endl;

    return 0;
}
